# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.mid_list = []
        if root:
            self.search(root)
        mid_list2, res_list = self.mid_list[:], []
        mid_list2.sort(key=lambda note: note.val)
        for i in range(len(mid_list2)):
            if mid_list2[i] is not self.mid_list[i]:
                res_list.append(i)
        mid_list2[res_list[0]].val, mid_list2[res_list[1]].val = \
            mid_list2[res_list[1]].val, mid_list2[res_list[0]].val

    def search(self, root: TreeNode):
        if root.left:
            self.search(root.left)
        self.mid_list.append(root)
        if root.right:
            self.search(root.right)
